package com.ljy.my_study.leetcode.寻宝;

import java.util.*;

/**
 * @author lijunying
 * @date 2020/7/29 8:45
 */
public class TestMain2 {

//    我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。
//
//    迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 'S' 表示），
//    和唯一的宝藏地点（用 'T' 表示）。但是，宝藏被一些隐蔽的机关保护了起来。
//    在地图上有若干个机关点（用 'M' 表示），只有所有机关均被触发，才可以拿到宝藏。
//
//    要保持机关的触发，需要把一个重石放在上面。迷宫中有若干个石堆（用 'O' 表示），
//    每个石堆都有无限个足够触发机关的重石。但是由于石头太重，我们一次只能搬一个石头到指定地点。
//
//    迷宫中同样有一些墙壁（用 '#' 表示），我们不能走入墙壁。剩余的都是可随意通行的点（用 '.' 表示）。
//    石堆、机关、起点和终点（无论是否能拿到宝藏）也是可以通行的。
//
//    我们每步可以选择向上/向下/向左/向右移动一格，并且不能移出迷宫。
//    搬起石头和放下石头不算步数。那么，从起点开始，我们最少需要多少步才能最后拿到宝藏呢？
//    如果无法拿到宝藏，返回 -1 。
//
//    示例 1：
//
//    输入： ["S#O", "M..", "M.T"]
//
//    输出：16
//
//    解释：最优路线为： S->O, cost = 4, 去搬石头 O->第二行的M, cost = 3,
//    M机关触发 第二行的M->O, cost = 3, 我们需要继续回去 O 搬石头。
//    O->第三行的M, cost = 4, 此时所有机关均触发 第三行的M->T, cost = 2，去T点拿宝藏。 总步数为16。

    public static void main(String[] args) {
//        String[] maze={"S#O", "M..", "M.T"};
//        String[] maze={"OOOOO","OS#OO","#O#TO","M#OOO"};
        String[] maze={"S.#.M","O.#.O","M.#.T"};
        System.out.println(new TestMain2().minimalSteps(maze));
    }

    public int minimalSteps(String[] maze) {
        int[] start=new int[2];
        int[] end=new int[2];
        List<int[]> buttons=new ArrayList<>();
        List<int[]> stones=new ArrayList<>();
        for(int i=0;i<maze.length;i++){
            for(int j=0;j<maze[0].length();j++){
                if(maze[i].charAt(j)=='S'){
                    start=new int[]{i,j};
                }else if(maze[i].charAt(j)=='T'){
                    end=new int[]{i,j};
                }else if(maze[i].charAt(j)=='M'){
                    buttons.add(new int[]{i,j});
                }else if(maze[i].charAt(j)=='O'){
                    stones.add(new int[]{i,j});
                }
            }
        }
        int[][] start2Points=bfs(start[0],start[1],maze);
        if(buttons.isEmpty()){
            return start2Points[end[0]][end[1]];
        }
        int[][][] button2Points=new int[buttons.size()][][];
        int len=Integer.MAX_VALUE;
        boolean[] buttonDownArr=new boolean[buttons.size()];
        int index=-1;
        for(int i=0;i<stones.size();i++){
            int[] s=stones.get(i);
            int aLen=start2Points[s[0]][s[1]];
            int bLen=Integer.MAX_VALUE;
            for(int j=0;j<buttons.size();j++){
                int[] b=buttons.get(j);
                if(button2Points[j]==null){
                    button2Points[j]=bfs(b[0],b[1],maze);
                }
                bLen=Math.min(bLen,button2Points[j][s[0]][s[1]]);
                if(bLen==button2Points[j][s[0]][s[1]]){
                    index=j;
                }
            }
            len=Math.min(len,aLen+bLen);
        }
        if(len<=0){
            return -1;
        }
        buttonDownArr[index]=true;
        int num=buttonDownArr.length-1;
        while(num>0){
            int nextLen=Integer.MAX_VALUE;
            for(int i=0;i<stones.size();i++){
                int[] s=stones.get(i);
                int aLen=button2Points[index][s[0]][s[1]];
                int bLen=Integer.MAX_VALUE;
                for(int j=0;j<buttons.size();j++){
                    if(buttonDownArr[j]){
                        continue;
                    }
                    int[] b=buttons.get(j);
                    if(button2Points[j]==null){
                        button2Points[j]=bfs(b[0],b[1],maze);
                    }
                    if(bLen>button2Points[j][s[0]][s[1]]){
                        bLen=button2Points[j][s[0]][s[1]];
                        index=j;
                    }
                }
                if(nextLen>aLen+bLen){
                    nextLen=aLen+bLen;
                }
            }
            if(nextLen<=0){
                return -1;
            }
            len+=nextLen;
            num--;
            buttonDownArr[index]=true;
        }

        int lastLen=button2Points[index][end[0]][end[1]];
        if(lastLen<=0){
            return -1;
        }
        len+=lastLen;
        return len;
    }

    int[] xArr={1,-1,0,0};
    int[] yArr={0,0,1,-1};

    private int[][] bfs(int x,int y,String[] maze){
        int xLen=maze.length;
        int yLen=maze[0].length();
        int[][] result=new int[xLen][yLen];
        for(int i=0;i<result.length;i++){
            Arrays.fill(result[i],-1);
        }

        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{x,y});
        result[x][y]=0;
        while(!queue.isEmpty()){
            int[] next=queue.poll();
            int k=xArr.length;
            for(int i=0;i<k;i++){
                int dx=next[0]+xArr[i];
                int dy=next[1]+yArr[i];
                if(dx==x&&dy==y){
                    continue;
                }
                if(inBound(dx,dy,xLen,yLen)){
                    if(maze[dx].charAt(dy)=='#'){
                        continue;
                    }
                    if(result[dx][dy]==-1){
                        result[dx][dy]=result[next[0]][next[1]]+1;
                        queue.offer(new int[]{dx,dy});
                    }else if(result[dx][dy]>result[next[0]][next[1]]+1){
                        result[dx][dy]=result[next[0]][next[1]]+1;
                        queue.offer(new int[]{dx,dy});
                    }
                }
            }
        }
        return result;
    }


    private boolean inBound(int x, int y,int n,int m) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
}
